package twobranchTree.isvalidbst;

import java.util.LinkedList;

import twobranchTree.preorderTraversal.TreeNode;

/**
 * @Date 2020/03/08
 * @author 王光浩
 * @Thinking 使用中序遍历遍历该二叉树，如果如果遍历所得的结果是一个升序的，则该树是一颗二叉搜索树。
 * @Analysis 时间复杂度O（2n），空间复杂度O（n）（不考虑堆栈的使用），n为节点总个数
 */
public class MyMethodOne {
	 LinkedList<Integer> res=new LinkedList<Integer>();		
	 public boolean isValidBST(TreeNode root) { 
		 if(root==null)return true;
		 recursively(root);
		 int last=res.poll();
		 //判断是否升序
		 while(!res.isEmpty()) {
			 int now=res.poll();
			 if(last>=now)return false;
			 last=now;
		 }
		 return true;
	 }
	 private void recursively(TreeNode root) {
		 if(root==null)return;
		 recursively(root.left);
		 res.add(root.val);
		 recursively(root.right);
	 }
}
